77. 组合

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/combinations/

题目描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

1
2
3
4
5
6
7
8
9
10
11
示例:
输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

组合问题和排列问题的区别

组合问题不考虑顺序问题，排列问题需要考虑顺序。

递归结构

递归边界

1
if i == k:

递归参数

  • step：访问的步数
  • n: 参数n传递
  • start：每一个步骤开始的数字
  • result：单次达到递归边界的结果
  • result_all：最终返回的结果

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def __init__(self):
        self.result_all = None
        self.visited = None
    
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        self.result_all = []
        self.dfs(0, n, k, 1, [])
        return self.result_all
        
    def dfs(self, step, n, k, start, result):
        if step == k:
            self.result_all.append(result[:])
            return
            
        for i in range(start, n + 1):
            result.append(i)
            self.dfs(step + 1, n, k, i + 1, result)
            result.pop()
        
        return